﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Runtime.Serialization;

namespace LostLib.Collections.Generic
{
	/// <summary>
	/// Represents directed acyclic graph
	/// </summary>
	/// <typeparam name="T">Type of node.</typeparam>
	/// <typeparam name="TList">Collection type to store edges</typeparam>
	[System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix"), Serializable]
	public class DirectedAcyclicGraph<T, TList>: Dictionary<T, TList>
		where TList: ICollection<T>
	{
		/// <summary>
		/// Constucts a DirectedAcyclicGraph
		/// </summary>
		public DirectedAcyclicGraph() : base() { }
		/// <summary>
		/// Deserializes a DirectedAcyclicGraph
		/// </summary>
		protected DirectedAcyclicGraph(SerializationInfo info, StreamingContext context): base(info, context)
		{

		}

		/// <summary>
		/// Performs topological sorting for given directed acyclic graph.
		/// </summary>
		/// <returns>Sorted list of nodes.</returns>
		public T[] TopologicalSort()
		{
			var dead = new HashSet<T>(); // ???
			var result = new T[this.Count];
			int dest = 0;

			Func<T, int> visit = null;
			visit = (dep) => {
				if (dead.Contains(dep)) return 0;

				dead.Add(dep);
				foreach (var child in this[dep])
					visit(child);

				result[dest++] = dep;
				return 0;
			};

			foreach (var dependency in this.Keys)
				visit(dependency);

			return result;
		}
	}
}
